// import java.util.ArrayList;
// import java.util.List;
// import java.util.Arrays;

// public class Solution {
//     public static List<int[]> findOriginalArrays(int[] a) {
//         int n = a.length;
//         List<int[]> result = new ArrayList<>();
//         boolean[] visited = new boolean[n];

//         for (int i = 0; i < n; i++) {
//             if (!visited[i]) {
//                 List<Integer> cycle = new ArrayList<>();
//                 int j = i;
//                 while (!visited[j]) {
//                     visited[j] = true;
//                     cycle.add(j);
//                     j = a[j];
//                 }
//                 if (cycle.size() > 1) {
//                     for (int k = 0; k < cycle.size() - 1; k++) {
//                         int temp = a[cycle.get(k)];
//                         a[cycle.get(k)] = a[cycle.get(k + 1)];
//                         a[cycle.get(k + 1)] = temp;
//                     }
//                     result.add(a.clone());
//                     for (int k = 1; k < cycle.size(); k++) {
//                         int temp = a[cycle.get(k - 1)];
//                         a[cycle.get(k - 1)] = a[cycle.get(k)];
//                         a[cycle.get(k)] = temp;
//                     }
//                 }
//             }
//         }

//         return result;
//     }

//     public static void main(String[] args) {
//         int[] a = {0, 1, 2, 4, 5, 3};
//         List<int[]> results = findOriginalArrays(a);
//         System.out.println(results.size());
//         for (int[] nums : results) {
//             System.out.println(Arrays.toString(nums));
//         }
//     }
// }

import java.util.*;

public class OriginalArrayFinder {

    public static List<List<Integer>> findOriginalArrays(int[] a) {
        // 1. 分解 a 的环结构
        List<List<Integer>> aCycles = findCycles(a);
        Map<Integer, List<List<Integer>>> cycleMap = groupCyclesByLength(aCycles);

        // 检查偶数环是否成对
        for (int len : cycleMap.keySet()) {
            if (len % 2 == 0 && cycleMap.get(len).size() % 2 != 0) {
                return new ArrayList<>();
            }
        }

        // 2. 处理奇数环和自环
        List<List<Integer>> originalCycles = new ArrayList<>();
        List<List<Integer>> selfCycles = new ArrayList<>();

        for (List<Integer> cycle : aCycles) {
            int len = cycle.size();
            if (len == 1) {
                selfCycles.add(cycle); // 自环单独处理
            } else if (len % 2 == 1) {
                // 处理奇数环
                List<Integer> originalCycle = generateOddLengthCycle(cycle);
                originalCycles.add(originalCycle);
            }
        }

        // 3. 生成自环的组合方式
        List<List<List<Integer>>> selfCycleCombinations = generateSelfCycleCombinations(selfCycles);

        // 4. 组合所有可能的环结构
        List<List<List<Integer>>> allCycleCombinations = new ArrayList<>();
        for (List<List<Integer>> selfCombo : selfCycleCombinations) {
            List<List<Integer>> combined = new ArrayList<>(originalCycles);
            combined.addAll(selfCombo);
            allCycleCombinations.add(combined);
        }

        // 5. 构建所有可能的 nums 数组并验证
        List<List<Integer>> solutions = new ArrayList<>();
        for (List<List<Integer>> cycles : allCycleCombinations) {
            int[] nums = buildNumsFromCycles(cycles, a.length);
            if (isValid(nums, a)) {
                solutions.add(arrayToList(nums));
            }
        }

        return solutions;
    }

    // ==== 新增方法：按环长度分组 ====
    private static Map<Integer, List<List<Integer>>> groupCyclesByLength(List<List<Integer>> cycles) {
        Map<Integer, List<List<Integer>>> map = new HashMap<>();
        for (List<Integer> cycle : cycles) {
            int len = cycle.size();
            map.computeIfAbsent(len, k -> new ArrayList<>()).add(cycle);
        }
        return map;
    }
    // 辅助方法：分解置换环
    private static List<List<Integer>> findCycles(int[] perm) {
        int n = perm.length;
        boolean[] visited = new boolean[n];
        List<List<Integer>> cycles = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                List<Integer> cycle = new ArrayList<>();
                int current = i;
                while (!visited[current]) {
                    visited[current] = true;
                    cycle.add(current);
                    current = perm[current];
                }
                cycles.add(cycle);
            }
        }
        return cycles;
    }

    // 生成奇数长度环的原始结构
    private static List<Integer> generateOddLengthCycle(List<Integer> cycle) {
        int len = cycle.size();
        int step = (len + 1) / 2;
        List<Integer> original = new ArrayList<>(len);
        int idx = 0;
        
        for (int i = 0; i < len; i++) {
            original.add(cycle.get(idx));
            idx = (idx + step) % len;
        }
        return original;
    }

    // 生成自环的组合方式
    private static List<List<List<Integer>>> generateSelfCycleCombinations(List<List<Integer>> selfCycles) {
        List<List<List<Integer>>> combinations = new ArrayList<>();
        int n = selfCycles.size();
        
        // 所有自环保持独立
        combinations.add(new ArrayList<>(selfCycles));
        
        // 生成所有两两配对组合
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                List<List<Integer>> combo = new ArrayList<>();
                // 添加未配对的环
                for (int k = 0; k < n; k++) {
                    if (k != i && k != j) {
                        combo.add(selfCycles.get(k));
                    }
                }
                // 添加配对后的环
                List<Integer> pair1 = Arrays.asList(selfCycles.get(i).get(0), selfCycles.get(j).get(0));
                List<Integer> pair2 = Arrays.asList(selfCycles.get(j).get(0), selfCycles.get(i).get(0));
                combo.add(pair1);
                combo.add(pair2);
                combinations.add(combo);
            }
        }
        return combinations;
    }

    // 从环结构构建数组
    private static int[] buildNumsFromCycles(List<List<Integer>> cycles, int length) {
        int[] nums = new int[length];
        for (List<Integer> cycle : cycles) {
            int size = cycle.size();
            for (int i = 0; i < size; i++) {
                int current = cycle.get(i);
                int next = cycle.get((i + 1) % size);
                nums[current] = next;
            }
        }
        return nums;
    }

    // 验证结果正确性
    private static boolean isValid(int[] nums, int[] a) {
        for (int i = 0; i < a.length; i++) {
            if (nums[nums[i]] != a[i]) {
                return false;
            }
        }
        return true;
    }

    // 转换工具方法
    private static List<Integer> arrayToList(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int num : arr) list.add(num);
        return list;
    }

    public static void main(String[] args) {
        int[] a = {0, 1, 2, 4, 5, 3};
        List<List<Integer>> solutions = findOriginalArrays(a);
        
        System.out.println("共有 " + solutions.size() + " 种解：");
        for (List<Integer> sol : solutions) {
            System.out.println(sol);
        }
    }
}